#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1


typedef struct Node
{
	int data;           //数据域
	struct Node* pnext; //指针域
} NODE, * PNODE;         //NODE等价于struct Node    PNODE等价于struct Node *


PNODE InitList_NODE()//创建链表
{
	int len; //用来存放有效节点的个数
	int val; //用来临时存放用户输入的结点的值
	//分配了一个不存放有效数据的头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("分配失败, 程序终止!\n");
		exit(-1);
	}
	// 定义一个临时结构体指针指向最后一个结点
	PNODE ptail = pHead;
	ptail->pnext = NULL;
	printf("请输入您需要生成的链表节点的个数: len = ");
	scanf("%d", &len);
	for (int i = 0; i < len; ++i)
	{
		printf("请输入第%d个节点的值: ", i + 1);
		scanf("%d", &val);
		//新结点
		PNODE pnew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pnew)
		{
			printf("分配失败, 程序终止!\n");
			exit(-1);
		}
		pnew->data = val;
		pnew->pnext = NULL;
		// 将之前的最后一个结点指向新结点
		ptail->pnext = pnew;
		//再将pTail指向新的最后一个结点
		ptail = pnew;
	}
	return pHead;
}

PNODE Merge_List(PNODE A,PNODE B)
{
	PNODE C = A;
	PNODE pa = A->pnext, pb = B->pnext;
	PNODE pc = C;
	while (pa && pb)
	{
		if (pa->data < pb->data)
		{
			pc->pnext = pa;
			pc = pa;
			pa = pa->pnext;
		}
		else
		{
			pc->pnext = pb;
			pc = pb;
			pb = pb->pnext;
		}
	}
	pc->pnext = pa ? pa : pb;
	free(B);
	A = B = NULL;
	return C;
}


void traverse_list(PNODE pHead)
{//遍历链表
	//获取第一个结点的地址
	PNODE p = pHead->pnext;
	while (p != NULL)
	{
		printf("%d  ", p->data);
		//将结点的指针域(下一个结点的地址)赋值给p
		p = p->pnext;
	}
	printf("\n");
}


int main()
{
	PNODE A=NULL, B=NULL, C=NULL;
	printf("     请选择对应操作:\n");
	printf("     1:创建并初始化链表 \n");
	printf("     2:合并链表 \n");
	printf("     3:遍历链表 \n");
	printf("     0:退出链表\n");
	while (1)
	{
		int x = 0;
		int n = 0;
		char ch = '0';
		scanf("%d", &n);
		switch (n)
		{
		case 0:
			x = 1;
			break;
		case 1:
			printf("初始化链表:");
			getchar();
			scanf("%c", &ch);
			if (ch == 'A')
			{
				A = InitList_NODE();
			}
			else if (ch == 'B')
			{
				B = InitList_NODE();
			}
			printf("     请选择对应操作:");
			break;
		case 2:
			C=Merge_List(A,B);
			printf("合并链表成功!\n");
			printf("     请选择对应操作:");
			break;
		case 3:
			printf("遍历链表:");
			getchar();
			scanf("%c", &ch);
			if (ch == 'A')
			{
				traverse_list(A);
			}
			else if (ch == 'B')
			{
				traverse_list(B);
			}
			else if (ch == 'C')
			{
				traverse_list(C);			
			}
			printf("     请选择对应操作:");
			break;
		}
		if (x == 1)
			break;
	}
}